今天的題單：

• Balanced Binary Tree

• Linked List Cycle

110. Balanced Binary Tree

題目敘述有點難懂，題目解釋和實作參考了這篇文章。

Balanced Binary Tree 的定義是：對於樹上的每個 node，各自的兩個子樹深度差不大於 1。

思路：是從最底層開始對每個 node 計算左右兩個子樹的深度，每往上一層就深度 +1。
用遞迴的方式實作，node 左右兩邊子樹的深度算出來之後就可以比較，大於 1 就可以標記為 unbalanced 不需要再做比較了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {

        // special case
        if (root == nullptr) {
            return true;
        }

        bool is_balanced = true;
        check_maxdepth(root, &is_balanced);

        return is_balanced;
    }
    
    // dfs
    int check_maxdepth(TreeNode* root, bool* res) {
        int l = 0;
        int r = 0;
        if (root->left != nullptr) {
            l = check_maxdepth(root->left, res);
        }
        if (root->right != nullptr) {
            r = check_maxdepth(root->right, res);
        }
        if (abs(r-l) > 1) {
            *res = false;
            return 0;
        }
        return max(l, r) + 1;
    }
};

141. Linked List Cycle

判斷 Linked list 是否有 cycle。

有 cycle 的特點：從第一個 node 開始走，如果有 cycle 的話就會走到同一個位置兩次。

思路 1：把記憶體位置拿去做 hash table，O(n) space。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode*, int> hashtbl;

        ListNode* ptr = head;

        while(ptr != nullptr) {
            if (hashtbl.find(ptr) == hashtbl.end()) {
                hashtbl[ptr] = 1;
            } else {
                return true;
            }
            ptr = ptr->next;
        }
        return false;
    }
};

思路 2：用 2 個 pointer（two pointer），O(1) space。兩個 pointer 走的速度一快一慢（slow pointer 一次走一個 node，fast pointer 一次走兩個 node），如果有 cycle 的話兩個 pointer 會在未來某個時間點重合在一起；沒有的話就會走到 list 最後（nullptr）。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // two pointer
        ListNode* slow;
        ListNode* fast;

        slow = fast = head;

        int counter = 1;

        // the fast ptr go 2 steps at a time, while the slow ptr goes 1 step
        while (fast != nullptr) {
            // step 1
            if (counter == 1) {
                fast = fast->next;
                if (fast == slow) {
                    return true;
                }
                counter--;
            } else {
                // step 2
                fast = fast->next;
                if (fast == slow) {
                    return true;
                }
                slow = slow->next;
                counter = 1;
            }
        }
        return false;
    }
};

我是把 fast == nullptr 當作是停止條件，當 fast 走到 list 最後的時候停止，如果 list 有 cycle 會在迴圈內偵測到。
Leetcode code sample 有另一個寫法，是把 slow == fast 當成迴圈停止條件。我覺得它寫的比較優雅一點，學到了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL)
            return false;
        ListNode* slow=head,*fast=head->next;

        while(slow!=fast)
        {
            if(fast==NULL || fast->next==NULL)
                return false;
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }
};